package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 1034. 边界着色
 * 给你一个大小为 m x n 的整数矩阵 grid ，表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。
 *
 * 当两个网格块的颜色相同，而且在四个方向中任意一个方向上相邻时，它们属于同一 连通分量 。
 *
 * 连通分量的边界 是指连通分量中的所有与不在分量中的网格块相邻（四个方向上）的所有网格块，或者在网格的边界上（第一行/列或最后一行/列）的所有网格块。
 *
 * 请你使用指定颜色 color 为所有包含网格块 grid[row][col] 的 连通分量的边界 进行着色，并返回最终的网格 grid 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：grid = [[1,1],[1,2]], row = 0, col = 0, color = 3
 * 输出：[[3,3],[3,2]]
 * 示例 2：
 *
 * 输入：grid = [[1,2,2],[2,3,2]], row = 0, col = 1, color = 3
 * 输出：[[1,3,3],[2,3,3]]
 * 示例 3：
 *
 * 输入：grid = [[1,1,1],[1,1,1],[1,1,1]], row = 1, col = 1, color = 2
 * 输出：[[2,2,2],[2,1,2],[2,2,2]]
 *
 *
 * 提示：
 *
 * m == grid.length
 * n == grid[i].length
 * 1 <= m, n <= 50
 * 1 <= grid[i][j], color <= 1000
 * 0 <= row < m
 * 0 <= col < n
 * @author SHM
 */
public class ColorBorder {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] check = new boolean[m][n];
        int g = grid[row][col];
        grid[row][col]=color;
        check[row][col] = true;
        int[][] direct = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
        for (int[] ints : direct) {
            int x = row+ints[0];
            int y = col+ints[1];
            if (x>=0&&x<m&y>=0&&y<n&&grid[x][y]==g&&!check[x][y]){
                colorBorder(grid,x,y,color);
                grid[x][y]=color;
                check[x][y] = true;
            }
        }
        return grid;
    }

    /**
     * 前言
     * 此题与搜索的经典题「200. 岛屿数量」较为类似，常规的思路是可以使用深度优先搜索或者广度优先搜索来寻找出位置 (\textit{row},\textit{col})(row,col) 的所在的连通分量，额外要做的是搜索的时候需要判断当前的点是否属于边界。如果属于边界，需要把该点加入到一个用来存所有边界点的数组中。当搜索完毕后，再将所有边界点的进行着色。
     *
     * 方法一：深度优先搜索
     * 思路及解法
     *
     * 我们用递归来实现深度优先搜索遍历连通分量，用一个大小和 \textit{grid}grid 相同的矩阵 \textit{visited}visited 来记录当前节点是否被访问过，并把边界点存入数组\textit{borders}borders 中。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(mn)O(mn)，其中 mm 和 nn 分别是 \textit{grid}grid 的行数和列数。在最坏情况下，我们需要访问到 \textit{grid}grid 中的每个点。
     *
     * 空间复杂度：O(mn)O(mn)。我们用一个与 \textit{grid}grid 相同大小的矩阵来存储每个点是否被遍历过，而其他的空间消耗，比如递归和用来存储所有边界点的数组，均不超过 O(mn)O(mn)。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/coloring-a-border/solution/bian-kuang-zhao-se-by-leetcode-solution-0h5l/
     * @param grid
     * @param row
     * @param col
     * @param color
     * @return
     */
    public int[][] colorBorder_1(int[][] grid, int row, int col, int color) {
        int m = grid.length;
        int n = grid[0].length;
        boolean[][] check = new boolean[m][n];
        int g = grid[row][col];
        check[row][col] = true;
        List<int[]> borders = new ArrayList<>();
        dfs(grid,row,col,check,borders,g);
        for (int i = 0; i < borders.size(); i++) {
            grid[borders.get(i)[0]][borders.get(i)[1]]=color;
        }
        return grid;
    }

    void dfs(int[][] grid,int x,int y,boolean[][] check,List<int[]> borders,int g){
        int m = grid.length;
        int n = grid[0].length;
        boolean isBorder = false;
        int[][] direct = new int[][]{{1,0},{0,1},{-1,0},{0,-1}};
        for (int[] ints : direct) {
            int nx = x+ints[0];
            int ny = y+ints[1];
            if (!(nx>=0&&nx<m&ny>=0&&ny<n&&grid[nx][ny]==g)){
                isBorder=true;
            }else if (!check[nx][ny]){
                check[nx][ny]=true;
                dfs(grid,nx,ny,check,borders,g);
            }
        }
        if (isBorder){
            borders.add(new int[]{x,y});
        }
    }
}
